The advent of global communications networks such as the Internet has facilitated access to enormous amounts of data. The world is populated with information sources where in many cases the data is represented differently from source to source. The free flow of information prevalent today in wired and wireless regimes demands that the source and destination be compatible insofar as storing and interpreting the data for use. A major problem facing companies and individuals today is that the data existing in one model/schema needs to be accessed via a different model/schema. However, such processes are being hampered by a largely disparate and ever-changing set of models/schemas. Such an example can be found in data warehousing where data is received from many different sources for storage and quick access from other sources. Converting data from one model to another model is not only time-consuming and resource intensive, but can be fraught with conversion problems.
Schema mappings specify the relationships between heterogeneous database sources and are used to support data transformation, data exchange, schema evolution, constraint checking, and other tasks. Mapping composition is an operation that takes as input two mappings mapAB and mapBC between schemas A, B, C and produces a single mapping mapAC that specifies the same set of constraints between A and C that is given by the combined mappings mapAB and mapBC.
To illustrate the use of mapping composition, consider the following schema evolution scenario. Assume that S1, S2, S3, S4 are versions of a schema used in successive releases of a product. The mapping map12 is used to migrate data from schema S1's format to schema S2's format. Similarly, mapping map23 is used to migrate data from schema S2's format to schema S3's format, and finally, map34 is used to migrate data from schema S3's format to schema S4's format. A conventional way of migrating the data from version S1 to version S4 is by executing map12, map23, map34 one by one, which is time-consuming and costly. To migrate the data from S1 to S4 in a single step, mapping composition is required. The mapping map14 can be obtained by first composing map12 and map23, and then composing the resulting mapping with map34.
Now suppose V1 is a view defined on S1 and map1V1 is a function. To migrate view V1 from S1 to S2, composition is again used. The inverse of mapping map12 is composed with map1V1 to obtain a mapping map2V1 from S2 to V1.
Algorithms for mapping composition are well-known for the case where each mapping is a function (i.e., maps one database state to exactly one database state, and both mappings have the same directionality). However, there is a substantial unmet need for an algorithm which is suitable for a broader class of mappings where one or both mappings are not functions.